package LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author attcat
 * ---做一个有趣的程序员
 * @date 2022-09-30 22:14
 * @description
 * 输入 N求 斐波那契  数列第N项目
 * f（0）=0
 * f（1）=1
 * f（n-2）+f（n-1） n>1
 */
public class Leetcode_100 {
    private Map<Integer,Integer> storeMap=new HashMap<>();

   public int recursive(int n){
        if(n==0) return 0;
        if(n==1) return 1;
     return  recursive(n-2)+recursive(n-1);
    }

    public int recursiveAddmap(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        if(null!=storeMap.get(n)){
            return storeMap.get(n);
        }else {
           int result= recursiveAddmap(n-2)+recursiveAddmap(n-1);
            storeMap.put(n,result);
            return result;
        }
    }

    public  int clibfor(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        int result =0;
        int pre=1;
        int prePre=0;
        for(int i=2;i<=n;++i){
            result=pre+prePre;
            prePre=pre;
            pre=result;
        }
        return result;
    }

    public static void main(String[] args) {
        Leetcode_100 Leetcode_100=new Leetcode_100();

        System.out.println(Leetcode_100.recursiveAddmap(100));
        System.out.println(Leetcode_100.clibfor(100));
    }

}
